Browsing by Author "Spirakis, Paul G."

Now showing items 1-20 of 38

    • Book Chapter  

      Algorithmic Game Theory and Applications 

      Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Spirakis, Paul G. (John Wiley & Sons, Inc., 2007)
      Methods from game theory and mechanism design have been proven to be a powerful mathematical tool in order to understand, control, and efficiently design dynamic, complex networks, such as the Internet. Game theory provides ...
    • Article  

      Approximate Equilibria and Ball Fusion 

      Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul G. (2003)
      We consider selfish routing over a network consisting of m parallel links through which n selfish users route their traffic trying to minimize their own expected latency. We study the class of mixed strategies in which the ...
    • Article  

      A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks 

      Chatzigiannakis, Ioannis; Dimitriou, Tassos D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2004)
      Smart Dust is comprised of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to accomplish a large sensing task. Smart ...
    • Article  

      A comparative study of protocols for efficient data propagation in smart dust networks 

      Chatzigiannakis, Ioannis; Dimitriou, Tassos D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2003)
      Smart Dust is comprised of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to accomplish a large sensing task. Smart ...
    • Article  

      Computing on a partially eponymous ring 

      Mavronicolas, Marios; Michael, Loizos; Spirakis, Paul G. (2009)
      We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...
    • Article  

      Computing on a partially eponymous ring 

      Mavronicolas, Marios; Michael, Loizos; Spirakis, Paul G. (2006)
      We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...
    • Article  

      A cost mechanism for fair pricing of resource usage 

      Mavronicolas, Marios; Panagopoulou, P. N.; Spirakis, Paul G. (2005)
      We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of m resources by n selfish agents. Each agent has an individual demand
    • Article  

      The cost of concurrent, low-contention Read&Modify&Write 

      Busch, Costas; Mavronicolas, Marios; Spirakis, Paul G. (2005)
      The possibility or impossibility and the corresponding costs of devising concurrent, low-contention implementations of atomic Read&Modify&Write (or RMW) operations in a distributed system were addressed. A natural class ...
    • Article  

      Cost sharing mechanisms for fair pricing of resource usage 

      Mavronicolas, Marios; Panagopoulou, P. N.; Spirakis, Paul G. (2008)
      We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of m resources by n selfish agents. Each agent has an individual demand
    • Article  

      Direct routing: Algorithms and complexity 

      Busch, Costas; Magdon-Ismail, M.; Mavronicolas, Marios; Spirakis, Paul G. (2006)
      Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be delivered to their destinations without collisions. We give a general treatment of three facets of direct ...
    • Article  

      Direct routing: Algorithms and complexity 

      Busch, Costas; Magdon-Ismail, M.; Mavronicolas, Marios; Spirakis, Paul G. (2004)
      Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be routed along specific paths to their destinations without conflicts. We give a general treatment of three ...
    • Conference Object  

      Efficiency of oblivious versus non-oblivious schedulers for optimistic, rate-based flow control 

      Fatourou, Panagiota; Mavronicolas, Marios; Spirakis, Paul G. (ACM, 1997)
      Lower and upper bounds on convergence complexity, under varying degrees of locality, for optimistic, rate-based flow control algorithms are established. It is shown that randomness can be exploited to yield an even simpler ...
    • Article  

      Efficiency of oblivious versus nonoblivious schedulers for optimistic, rate-based flow control 

      Fatourou, Panagiota; Mavronicolas, Marios; Spirakis, Paul G. (2005)
      Two important performance parameters of distributed, rate-based flow control algorithms are their locality and convergence complexity. The former is characterized by the amount of global knowledge that is available to their ...
    • Article  

      Extreme Nash equilibria 

      Gairing, M.; Lucking, T.; Mavronicolas, Marios; Monien, Burkhard; Spirakis, Paul G. (2003)
      We study the combinatorial structure and computational complexity of extreme Nash equilibria, ones that maximize or minimize a certain objective function, in the context of a selfish routing game. Specifically, we assume ...
    • Article  

      A glimpse at Christos H. Papadimitriou 

      Mavronicolas, Marios; Spirakis, Paul G. (2009)
      Christos H. Papadimitriou is one of the most influential and colorful researchers in Computer Science today. This glimpse is the outcome of a modest attempt of us to a biographical introduction to Christos, which we have ...
    • Article  

      A graph-theoretic network security game 

      Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Philippou, Anna; Spirakis, Paul G. (2005)
      Consider a network vulnerable to viral infection. The system security software can guarantee safety only to a limited part of the network. We model this practical network scenario as a non-cooperative multi-player game on ...
    • Article  

      A graph-theoretic network security game 

      Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Philippou, Anna; Spirakis, Paul G. (2008)
      Consider a network vulnerable to viral infection, where the security software can guarantee safety only to a limited part of it. We model this practical network scenario as a non-cooperative multi-player game on a graph, ...
    • Article  

      The impact of network structure on the stability of greedy protocols 

      Koukopoulos, D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2003)
      A packet-switching network is stable if the number of packets in the network remains bounded at all times. A very natural question that arises in the context of stability and instability properties of such networks is how ...
    • Article  

      The impact of network structure on the stability of greedy protocols 

      Koukopoulos, D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2005)
      Some examples of the impact network structure has on stability behavior of greedy protocols and networks were presented. An important problem was to study the impact of network structure parameters on other greedy protocols. ...
    • Article  

      The increase of the instability of networks due to Quasi-Static link capacities 

      Koukopoulos, D.; Mavronicolas, Marios; Spirakis, Paul G. (2007)
      In this work, we study the impact of the dynamic changing of the network link capacities on the stability properties of packet-switched networks. Especially, we consider the Adversarial, Quasi-Static Queuing Theory model, ...